# 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
# 
#  
# 
#  示例 1： 
#  
#  
# 输入：l1 = [1,2,4], l2 = [1,3,4]
# 输出：[1,1,2,3,4,4]
#  
# 
#  示例 2： 
# 
#  
# 输入：l1 = [], l2 = []
# 输出：[]
#  
# 
#  示例 3： 
# 
#  
# 输入：l1 = [], l2 = [0]
# 输出：[0]
#  
# 
#  
# 
#  提示： 
# 
#  
#  两个链表的节点数目范围是 [0, 50] 
#  -100 <= Node.val <= 100 
#  l1 和 l2 均按 非递减顺序 排列 
#  
# 
#  Related Topics 递归 链表 👍 3659 👎 0
from typing import Optional

from LeetCode.Test.LinkTool import ListNode, LinkedListTool, Link


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(-1)
        curr = dummy
        while list1 and list2:
            if list1.val > list2.val:
                next_node2 = list2.next
                # 把小的移动到dummy后面
                curr.next = list2
                list2.next = None
                # 移动list2指针
                list2 = next_node2
            else:
                next_node1 = list1.next
                curr.next = list1
                list1.next = None
                # 移动list1指针
                list1 = next_node1
            curr = curr.next
        # 检查哪个还有剩余,把剩余的直接接到后面就行了
        if list1:
            curr.next = list1
        if list2:
            curr.next = list2
        return dummy.next


# leetcode submit region end(Prohibit modification and deletion)
Link.each(Solution().mergeTwoLists(LinkedListTool([1, 3, 5, 7, 9]), LinkedListTool([2, 4, 6, 8, 10])))
